package 链表;

public class NC3链表环的入口 {

    /**
     * 对于一个给定的链表，返回环的入口节点，如果没有环，返回null
     * 拓展：
     * 你能给出不利用额外空间的解法么？
     */

    public ListNode detectCycle(ListNode head) {

        ListNode slow=head;
        ListNode fast=head;

        while (fast!=null&&fast.next!=null){

            slow=slow.next;
            fast=fast.next.next;

            if(fast==slow){
                break;
            }
        }

        if(fast==null||fast.next==null){
            return null;
        }

        ListNode temp=head;

        while (temp!=slow){
            temp=temp.next;
            slow=slow.next;
        }

        return slow;
    }

}
